package com.fenqing.leetcode.code.t600_700;

import com.fenqing.annotations.Execute;
import com.fenqing.core.Topic;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Topic658 extends Topic {

    /**
     * 构造器
     *
     * @param input1 输入1
     * @param input2 输入2
     * @param input3 输入3
     */
    public Topic658(String input1, String input2, String input3) {
        super(input1, input2, input3);
    }

    /**
     * 给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
     * 整数 a 比整数 b 更接近 x 需要满足：
     * |a - x| < |b - x| 或者
     * |a - x| == |b - x| 且 a < b
     * 示例 1：
     * 输入：arr = [1,2,3,4,5], k = 4, x = 3
     * 输出：[1,2,3,4]
     * 示例 2：
     * 输入：arr = [1,2,3,4,5], k = 4, x = -1
     * 输出：[1,2,3,4]
     * @param arr arr
     * @param k k
     * @param x x
     * @return return
     */
    @Execute
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = binarySearch(arr, x);
        int right = left + 1;
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            if(left < 0) {
                result.add(arr[right]);
                right++;
            } else if (right >= arr.length) {
                result.add(arr[left]);
                left--;
            } else {
                int leftVal = arr[left];
                int rightVal = arr[right];
                int leftNum = Math.abs(x - leftVal);
                int rightNum = Math.abs(x - rightVal);
                if (leftNum <= rightNum) {
                    result.add(leftVal);
                    left--;
                } else {
                    result.add(rightVal);
                    right++;
                }
            }
        }
        result.sort(Comparator.comparing(Integer::valueOf));
        return result;
    }

    public int binarySearch(int[] arr, int x){
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            int midVal = arr[mid];
            if (midVal == x) {
                return mid;
            } else if (midVal > x) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return arr[left] > x ? left - 1 : left;
    }

    public static void main(String[] args) {
        Topic658 topic658 = new Topic658(
                """
                        [1,3]
                        """,
                "1",
                "2"
        );
        List<Integer> run = topic658.run();
        System.out.println(run);
    }
}
